package promote.brozen.algorithm.tree.binary;

import java.util.function.Consumer;

/**
 * 递归实现的二叉树遍历
 * @author Brozen
 * @date 2019/12/19 9:10 AM
 */
public class RecursionBinaryTreeWalker {

    /**
     * 前序遍历节点
     * 先根节点，后左子树，最后右子树
     */
    public static <K, S extends BinaryTreeNode<K, S>> void preOrderTraversal(BinaryTreeNode<K, S> root, Consumer<K> consumer) {
        if (root == null || consumer == null) {
            return;
        }

        consumer.accept(root.getKey());
        preOrderTraversal(root.getLeftChild(), consumer);
        preOrderTraversal(root, consumer);
    }

    /**
     * 中序遍历节点
     * 先左子树，后根节点，最后右子树
     */
    public static <K, S extends BinaryTreeNode<K, S>> void inOrderTraversal(BinaryTreeNode<K, S> root, Consumer<K> consumer) {
        if (consumer == null || root == null) {
            return;
        }

        inOrderTraversal(root.getLeftChild(), consumer);
        consumer.accept(root.getKey());
        inOrderTraversal(root.getRightChild(), consumer);
    }

    /**
     * 后序遍历节点
     * 先左子树，后右子树，最后根节点
     */
    public static <K, S extends BinaryTreeNode<K, S>> void postOrderTraversal(BinaryTreeNode<K, S> root, Consumer<K> consumer) {
        if (consumer == null || root == null) {
            return;
        }

        inOrderTraversal(root.getLeftChild(), consumer);
        inOrderTraversal(root.getRightChild(), consumer);
        consumer.accept(root.getKey());
    }
}
